class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.__size = [1] * n

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a

    def merge(self, a, b):
        s, f = self.find(a), self.find(b)
        if s == f: return
        ss, ff = s, f
        if self.__size[s] > self.__size[f]:
            ss, ff = f, s
        self.parent[ss] = ff
        self.__size[ff] += self.__size[ss]

    def size(self, a):
        return self.__size[self.find(a)]